A conventional RFID tag typically comprises an integrated circuit transceiver capable of transmitting a unique serial number or other identifying information to a nearby reader in response to a query from the reader. Many RFID tags are “passive” in that they do not include a battery or other power source, but instead obtain the power necessary to operate from the query signal itself.
Ongoing RFID tag development efforts have led to significant cost and size reductions, which should result in a rapid proliferation of RFID tags into many new areas of use. For example, RFID tags are expected to replace printed barcodes in consumer product applications. The Electronic Product Code (EPC) tag is a form of RFID device that is emerging as a successor to the printed barcode. EPC tags are an evolving standard under development by an organization called EPCglobal, a joint venture between the UCC and EAN, the organizations that oversee barcode standards in the U.S. and Europe, respectively. An EPC is the form of identifier that an individual EPC tag emits as prescribed by the EPCglobal standard. An EPC includes not just the information contained in a conventional printed barcode, namely the manufacturer and type of a particular product, but also a unique serial number. Additional details can be found in the current version of the EPCglobal standard document, “EPC™ Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz-960 MHz,” Version 1.0.8, 2005.
The unique serial number of an EPC tag associated with an object can serve as a pointer to a database entry containing a detailed history of the object. Thanks to the features of automated scanning and unique identification, RFID systems promise fine-grained tracking of inventory on an unprecedented scale.
Some commercial segments, like the pharmaceutical industry, are coming to view EPC tags as an anti-counterfeiting tool. EPC tags are a potent mechanism for object identification, and can facilitate the compilation of detailed object histories and pedigrees. They are poor authenticators, though, as they possess no explicit authentication functionality. The EPCglobal standards prescribe no mechanism for EPC readers to authenticate the validity of the tags they scan. An EPC tag emits its EPC promiscuously, i.e., to any querying reader. Readers accept the validity of the EPCs they scan at face value. Thus, EPC tags are vulnerable to counterfeiting or other types of cloning attacks.
An attacker can learn an EPC tag's essential data, its EPC, simply by scanning it or by gaining access to an appropriate tag database. The term “skimming” is used herein to denote the process of scanning an EPC tag to obtain its EPC for the purpose of cloning the tag. Furthermore, if the unique identifiers in a manufacturer's EPCs are not random, e.g., if they are sequential, then an attacker that sees an EPC on one item can guess or fabricate another valid EPC. In brief, “identity theft” of EPC tags is a straightforward matter because EPCs are data objects that are easily separable from EPC tags.
Some commercially available RFID tags can perform cryptographic challenge-response protocols. Such tags offer resistance to cloning attacks involving skimming. They typically cost significantly more than EPC tags, though, and may therefore be practical only for certain niche applications.
Privacy-protecting authentication protocols for RFID tags are described in S. E. Sarma et al., “Radio-frequency-identification security risks and challenges,” RSA Laboratories, CryptoBytes, 6(1), 2003, and S. A. Weis et al., “Security and privacy aspects of low-cost radio frequency identification systems,” First International Conference on Security in Pervasive Computing, 2003. However, these protocols utilize cryptographic hash functions, and thus may be unsuitable for Class-1 EPC tags.
The above-cited U.S. patent application Ser. No. 10/782,309 discloses an authentication approach referred to as “minimalist” cryptography, including a security model for RFID environments that permits a form of dynamic challenge-response protocol without the use of complex cryptographic operations. However, even this minimalist approach may require greater tag resources than are available in the current generation of EPC tags.
Another approach, known as “yoking,” allows a pair of tags with minimal resources to construct a one-time proof that they have been read simultaneously. See A. Juels, “‘Yoking-proofs’ for RFID tags,” PerCom Workshops 2004, pp. 138-143, IEEE Computer Society, 2004. The techniques underlying yoking could be used to enable tags to authenticate themselves to readers, but aim to secure only one-time use, rather than repeated use.
There is a considerable body of research on the design of lightweight public-key encryption and digital-signing algorithms, largely intended for use in smart cards and similarly small computational devices. See, e.g., J. Stern et al., “Cryptanalysis of the OTM signature scheme from FC '02,” R. Wright, editor, Financial Cryptography '03, pp. 138-148, Springer-Verlag, 2003, LNCS No. 2742. However, even the most lightweight of these many schemes is likely to be well beyond the capabilities of small RFID tags for quite some time to come. A related area is security for sensor networks. While lightweight, these devices are still more capable than RFID tags, as they typically include their own power sources. Although recent work has led to more compact implementations of symmetric-key primitives like AES for RFID tags, these are still well beyond the reach of Class-1 EPC tags today, and unsupported in the EPCglobal standard.
Accordingly, a need exists for techniques for authenticating EPC tags and other types of RFID devices, so as to prevent counterfeiting or other cloning attacks without requiring cryptographic operations.